The present invention relates to content addressable memory (CAM). More specifically, the present invention relates to a ternary CAM architecture implementing a split word line scheme and a folded bit line architecture.
A content addressable memory (CAM) is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. CAMs provide benefits over other memory search algorithms by simultaneously comparing the desired information (i.e., data being stored within a given memory location) against the entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers and switches, computer systems and other devices that require rapid content searching.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., random access memory (RAM), dynamic RAM (DRAM), etc.). For example, data is stored in a RAM in a particular location, called an address. During a memory access, the user supplies an address and reads into or gets back the data at the specified address.
In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected by an address bus, or the data can be written into the first empty memory location. Every location has a pair of status bits that keep track of whether the location is storing valid information in it or is empty and available for writing.
Once information is stored in a memory location, it is found by comparing every bit in memory with data placed in a match detection circuit. When the content stored in the CAM memory location does not match the data placed in the match detection circuit, the CAM device returns a no match indication. When the content stored in the CAM memory location matches the data placed in the match detection circuit, the CAM device returns a match indication. In addition, the CAM may return the identification of the address location in which the desired data is stored. Thus, with a CAM, the user supplies the data and gets back the address if there is a match found in memory.
Generally, CAM includes an array of CAM cells arranged in row and column lines. Each CAM cell stores one bit of digital data and includes a circuit to allow comparing the stored data with the externally provided search data. One or more bits of information in a row constitute a word. A CAM compares a search word with a row of words stored within the CAM. During a search and compare operation, an indicator associated with each stored word produces a comparison result indicating whether or not the search word matches the stored word.
The CAM structure can be made more powerful and useful by incorporating additional logic whereby a xe2x80x9cdon""t carexe2x80x9d state can be presented in addition to the xe2x80x9c0xe2x80x9d state and xe2x80x9c1xe2x80x9d state. A xe2x80x9cdon""t carexe2x80x9d state can be stored which allows certain bits of data to be skipped from search operations. The xe2x80x9cdon""t carexe2x80x9d state can be stored by having similar charges on the two storage capacitors. In addition, additional flexibility results from the ability to store the xe2x80x9cdon""t carexe2x80x9d state in the memory itself. The use of the xe2x80x9cdon""t carexe2x80x9d state means that the CAM device has xe2x80x9cternaryxe2x80x9d storage capabilities.
Some of the prior art CAM cells use static storage while others use a dynamic storage element. Dynamic storage elements occupy a smaller area and are therefore preferable to obtain a large memory capacity on a single integrated circuit chip. In addition, a dynamic storage cell is more efficient for ternary storage as described above.
A dynamic CAM is cell suitable for constructing relatively high-speed and large capacity CAM arrays, having binary and ternary storage capacity. Furthermore, the CAM cell also provides a relatively stable voltage level at the match line and a relatively stable capacitance at the bit lines.
A conventional CAM cell 10 is illustrated in FIG. 1. As shown in this figure, the CAM cell 10 includes first and second storage device(s) C1, C2 in the form of capacitors. Each storage device C1, C2 is capable of storing a charge representing a binary xe2x80x981xe2x80x99 or a xe2x80x980xe2x80x99. In a binary configuration, the CAM cell 10 stores a binary bit of digital information as xe2x80x980xe2x80x99 on C1 and xe2x80x981xe2x80x99 on C2 or xe2x80x981xe2x80x99 on C1 and xe2x80x980xe2x80x99 on C2. Furthermore, in a ternary configuration, the CAM cell 10 attains an additional xe2x80x9cdon""t carexe2x80x9d state when both storage devices C1, C2 store a xe2x80x980xe2x80x99. Further shown in FIG. 1 are the first and second cell nodes N1, N2 which carry signal levels corresponding to the data stored in the CAM cell 10. The two cell nodes N1, N2 are accessible for write and read operations via first and second access transistors T1, T2, respectively. The remaining two terminals of the storage device C1, C2 are connected to the cell plate voltage terminal VCP. The source terminals of the access transistors T1, T2 are connected to the nodes N1, N2 whereas their drain terminals are connected to the first and second bit lines BL1, BL2. The first and second access transistors T1, T2 are responsive to and have their gate terminals connected to a word line WL.
Also shown in FIG. 1 is a comparing circuit having first and second pull-down circuits PD1, PD2. The first pull-down circuit PD1 consists of third and fourth pull-down transistors T3, T4 respectively connected in series between a match line ML and a discharge line DL. The drain terminal of the third pull-down transistor T3 is connected to the source terminal of the fourth pull-down transistor T4. The third pull-down transistor T3 is responsive to the first cell node N1 by having its gate connected to node N1. The gate of the fourth pull down transistor T4 is connected to a first search line SL1. Similarly, the second pull-down circuit PD2 consists of fifth and sixth pull-down transistors T5, T6 respectively connected between the match line ML and the discharge line DL. The drain terminal of the fifth pull-down transistor T5 is connected to the source terminal of the sixth pull-down transistor T6. The gate terminal of the fifth pull-down transistor T5 is connected to the second node N2 and the gate of the sixth pull-down transistor T6 is connected to a second search line SL2. The combination of the first and second pull-down circuits PD1, PD2 provides a comparison between complementary data bits stored in the storage devices C1, C2 and complementary search bits carried on SL1 and SL2. The result of such comparison is reflected in the match line ML being discharged by the first or the second pull-down circuit PD1, PD2 if there is a data mismatch (as will be further described below).
A CAM device performs three distinct operations, a write operation, read operation and search and compare operation. The conventional CAM cell 10 has two storage devices C1, C2 for storing two data bits which have independent values from each other. The storage devices C1, C2 are each connected to bit lines BL1, BL2 through access transistors T1, T2, respectively. The bit lines BL1, BL2 allow for data to be independently written to the corresponding storage devices C1, C2. The two search lines SL1, SL2 connected to the pull-down circuits PD1, PD2 are used for distinct search and compare operations. A search operation consists of comparing the search bits carried on the search lines SL1, SL2 to data bits stored in the first and second storage devices C1, C2. The comparing circuit couples the match line ML to the discharge line DL if a mismatch occurs between the first and second search bits and the respective first and second data bits, and when the first and second data bits have complementary values.
Furthermore, FIG. 1 discloses a CAM cell 10 with an open bit line architecture. Each bit line shown in FIG. 1 of the conventional CAM cell 10 is connected to a separate sense amplifier SA1, SA2. Furthermore, each storage device C1, C2 is coupled to respective bit lines by access transistors T1, T2 which have their gates connected to the same word line WL. The circuit in FIG. 1 has a sense amplifier for each bit line in the CAM array architecture.
The present invention provides a ternary CAM architecture which implements a split word line scheme and a folded bit line architecture. The split word line scheme and folded bit line array architecture provides improved noise immunity and consistency with commodity DRAM architectures. Furthermore, the present invention reduces the high sense amplifier count typically associated with a ternary CAM memory array.
In accordance with an aspect of the present invention, there is provided a CAM cell for storing and accessing ternary data which comprises a split word line scheme. The present invention reduces the number of sense amplifiers by at least half by allowing one sense amplifier to sense the data from multiple storage devices. This is accomplished by using a split word line to access the storage devices independently of each other as well as improving the sensed signal in array CAMs by reducing noise.
The foregoing and other advantages and features of the invention will become more apparent from the following detailed description of exemplary embodiments provided below with reference to the accompanying drawings in which: